A. Field of Invention
The present invention relates to the field of communication networks, and more particularly to a self-routing multicast network architecture based on recursive network decompositions of reverse banyan multicast networks.
B. Description of Related Art
Multicast, or one-to-many, communication is one of the most important collective communication operations and is highly demanded in parallel applications as well as in other communication environments. Multicast, for example, is required to make updates in replicated and distributed databases. In addition, multiprocessor systems use multicasting for cache coherency to aid message passing, and multicasting is a critical operation for video/tele-conference calls and video-on-demands services in telecommunication environments. Those skilled in the art will recognize that providing multicast support at the hardware interconnection network level is the most efficient way support such communication operations. Generally, switching networks that realize these types of arbitrary multicast communications without any blocking, or multiple rerouting, are referred to as multicast networks.
Another notable feature in multicast network design is self-routing. Self-routing is a routing scheme that permits switch settings to take place during the routing sequence. This allows designers to create a network with faster switch settings, scalability, and less hardware complexity. Conventionally, however, most self-routing network designs relate to permutation networks, and not multicast networks. W. J. Cheng and W. T. Chen, "A New Self-Routing Permutation Network," IEEE Trans. Computers, Vol. C-45, No. 5, pp. 630-636, 1996 [hereinafter Cheng and Chen] for example, discloses a self-routing permutation network constructed of reverse banyan networks, and is herein incorporated by reference. Permutation networks, as described by Cheng and Chen, do not provide a one to many broadcast output, but can only route n distinct input packets to n distinct output ports.
Others have attempted to implement multicast networks using recursive designs, but these previous attempts resulted in high propagation delays and expensive hardware costs. In an article by D. Nassimi and S. Sahni entitled, "Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network," Journal of the Association for Computing Machinery, Vol. 29, No. 3, pp. 642-667, July 1982, for example, the authors proposed a n.times.n multicast network that used O(k n.sup.1+l/k log n) 2.times.2 switches. This network had O(k log n) depth and O(k log n) set-up time for any k, where 1.ltoreq.k.ltoreq.log n. Nassimi and Sahni also disclosed a routing algorithm that relied on a cube or a perfect shuffle connected parallel computer consisting of O(n.sup.1+l/k) processors, which in turn caused the routing process to have a gate delay of O(k log.sup.2 n). In another article entitled "Design of Efficient and Easily Routable Generalized Connectors," IEEE Trans. Communications, Vol. COM-43, No. 2/3/4, pp. 646-650, 1995, C. Lee and A. Y. Oruc disclosed a multicast network with a special built-in routing circuit, and is herein incorporated by reference. This network used O(n log.sup.2 n) logic gates, and had O(log.sup.2 n) gate delay and O(log.sup.3 n) set-up time (where the unit of time is a gate delay). Each of these proposed networks had high gate delays and more substantial hardware costs than are generally desired by network designers.
Therefore, a need exists for a network architecture capable of handling multicast connections in a self-routing manner without the gate delays and hardware costs of conventional designs. Additionally, a need exists for a multicast network with the modularity and scalability not offered by conventional designs.